# 方法一：暴力匹配
"""
思路：从字符串的最长可能前缀（即长度为 len(s) - 1）开始，
依次检查该前缀是否也是后缀，若不是则缩短前缀长度继续检查，直至找到满足条件的最长前缀或确定不存在。
"""
class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        for i in range(n - 1, 0, -1):
            if s[:i] == s[-i:]:
                return s[:i]
        return ""

# 方法二：KMP算法
"""
思路：KMP 算法中的 next 数组可以记录字符串中每个位置之前的子串的最长公共前后缀长度。
因此，我们可以利用 next 数组来找到字符串 s 的最长快乐前缀。
"""
class Solution:
    def longestPrefix(self, s: str) -> str:
        i = 1
        lenght = 0
        next = [0]
        while i < len(s):
            if s[i] == s[lenght]:
                lenght += 1
                next.append(lenght)
                i += 1
            else:
                if lenght == 0:
                    next.append(0)
                    i += 1
                else:
                    lenght = next[lenght - 1]
        # next[n - 1] 存储的是整个字符串 s 的最长公共前后缀长度
        # 根据这个长度截取字符串 s 的前缀，即为最长快乐前缀
        return s[:next[len(s) - 1]]
